# 10台阶，每次上1个台阶或者2个台阶，为一共有多少种走法
# 3
# 1 1 1
# 2 1
# 1 2
# f(n) = f(n-1) + f(n-2) 最后一步可能走一步或者两步，倒推会去求
# 临界条件
# n=0,f(0)=0
# n=1,f(1)=1
# n=2,f(2)=2
def stair(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    return stair(n - 1) + stair(n - 2)


print("楼梯有%d阶的时候，有%d种走法" % (10, stair(10)))

a = [0, 1, 2]
for i in range(3, 11):
    a.append(a[i-1] + a[i-2])
    print("楼梯有%d阶的时候，有%d种走法" % (10, a[-1]))
